package leetcode101.dynamic_planning;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code14
 * @Description 416. 分割等和子集
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 注意:
 *
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * 示例 1:
 *
 * 输入: [1, 5, 11, 5]
 *
 * 输出: true
 *
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 *  
 *
 * 示例 2:
 *
 * 输入: [1, 2, 3, 5]
 *
 * 输出: false
 *
 * 解释: 数组不能分割成两个元素和相等的子集.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-16 8:19
 */
public class Code14 {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 2, 1, 1};
        System.out.println(canPartition(nums));
    }

    public static boolean canPartition(int[] nums) {
        int sum = getSum(nums, 0, nums.length - 1);
        if ((sum & 1) == 1) {
            return false;
        }
        sum /= 2;
        boolean[][] dp = new boolean[nums.length + 1][sum + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (nums[i - 1] == j) {
                    dp[i][j] = true;
                } else if (nums[i - 1] > j) {
                    dp[i][j] = dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
                }
            }
        }
        return dp[nums.length][sum];
    }

    public static int getSum(int[] arr, int low, int high) {
        int temp = 0;
        for (int i = low; i <= high; i++) {
            temp += arr[i];
        }
        return temp;
    }

}
/*
思路一是排序，二分查找
发现对于{1, 1, 2, 2}这种是不行的
本道题的本质相当于01背包问题，设数组的总和为sum
只需要选取一部分数字凑够sum/2即可，凑成了返回true 凑不成返回false
dp[i][j] 代表了前i个物品能否凑够价格为j
那么dp[i][j]的计算如下：
如果第 i - 1 个物品的价值刚好等于 j 那么 为true
如果第 i - 1 个物品的价值大于 j 那么 该物品一定不能选，dp[i][j] = dp[i - 1][j]
如果第 i - 1 个物品的价值小于 j 那么 该物品可以选也可以不选 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
 */